Large cycles in random generalized Johnson graphs

This paper studies thresholds in random generalized Johnson graphs for containing large cycles, i.e. cycles of variable length growing with the size of the graph. Thresholds are obtained for different growth rates.     

Matroid bases with cardinality constraints on the intersection

Mathematical Programming - Given two matroids $$\mathcal {M}_{1} = (E, \mathcal {B}_{1})$$ and $$\mathcal {M}_{2} = (E, \mathcal {B}_{2})$$ on a common ground set E with base sets $$\mathcal...     

Correction to: Idealness of k-wise intersecting families

Mathematical Programming - A Correction to this paper has been published: 10.1007/s10107-020-01587-x     

Idealness of k-wise intersecting families

Mathematical Programming - A clutter is k-wise intersecting if every k members have a common element, yet no element belongs to all members. We conjecture that, for some integer $$k\ge 4$$ , every...     

Analysis of Decomposition Algorithms with Benders Cuts for p-Median Problem

In this paper the algorithms for solving the p-median problem based on the Benders decomposition are investigated. A family of problems hard for solving with such algorithms is constructed and then generalized to a special NP-hard case of the p-median problem. It is shown that the effectiveness of the considered algorithms depends on the choice of the optimal values of the dual variables used in Benders cuts. In particular, the depth of the cuts can be equal to one.     

NECESSARY CONDITIONS FOR OPTIMAL CONTROLS OF SEMILINEAR ELLIPTIC VARIATIONAL INEQUALITIES INVOLVING STATE CONSTRAINT

This paper deals with maximum principle for some optimal control problem governed by some elliptic variational inequalities. Some state constraints are discussed. The basic techniques used here are based on those in [1] and a new penalty functional defined in this paper.     

Geometric quadrisection in linear time, with application to VLSI placement

We consider the following problem: given a set of points in the plane, each with a weight, and capacities of the four quadrants, assign each point to one of the quadrants such that the total weight of points assigned to a quadrant does not exceed its capacity, and the total distance is minimized.

This problem is most important in placement of VLSI circuits and is likely to have other applications. It is NP-hard, but the fractional relaxation always has an optimal solution which is “almost” integral. Hence for large instances, it suffices to solve the fractional relaxation. The main result of this paper is a linear-time algorithm for this relaxation. It is based on a structure theorem describing optimal solutions by so-called “American maps” and makes sophisticated use of binary search techniques and weighted median computations.

This algorithm is a main subroutine of a VLSI placement tool that is used for the design of many of the most complex chips.     

Valuations and Busemann–Petty type problems

Projection and intersection bodies define continuous and GL(n) contravariant valuations. They played a critical role in the solution of the Shephard problem for projections of convex bodies and its dual version for sections, the Busemann–Petty problem. We consider the question whether ΦKΦL implies V(K)V(L), where Φ is a homogeneous, continuous operator on convex or star bodies which is an SO(n) equivariant valuation. Important previous results for projection and intersection bodies are extended to a large class of valuations.     

Complete decomposition of Dickson-type polynomials and related Diophantine equations

We characterize decomposition over C of polynomials defined by the generalized Dickson-type recursive relation (n?1)

     

Some new results in multiplicative and additive Ramsey theory

There are several notions of largeness that make sense in any semigroup, and others such as the various kinds of density that make sense in sufficiently well-behaved semigroups including and . It was recently shown that sets in which are multiplicatively large must contain arbitrarily large geoarithmetic progressions, that is, sets of the form , as well as sets of the form . Consequently, given a finite partition of , one cell must contain such configurations. In the partition case we show that we can get substantially stronger conclusions. We establish some combined additive and multiplicative Ramsey theoretic consequences of known algebraic results in the semigroups and , derive some new algebraic results, and derive consequences of them involving geoarithmetic progressions. For example, we show that given any finite partition of there must be, for each , sets of the form together with , the arithmetic progression , and the geometric progression in one cell of the partition. More generally, we show that, if is a commutative semigroup and a partition regular family of finite subsets of , then for any finite partition of and any , there exist and such that is contained in a cell of the partition. Also, we show that for certain partition regular families and of subsets of , given any finite partition of some cell contains structures of the form for some .